Cache is used to increase the speed with which a computer accesses data with minimal added expense. It is a block of memory that is much smaller and faster than a computer's main memory. A cache stores a group of byes in a small, fast memory. Once those bytes are no longer needed, they are flushed out to the larger, slower memory, and another set of bytes can be loaded into the cache.
The concept of caching is based on the observation that computers usually access data by temporal and spatial locality. In other words, if a byte has been accessed recently, then the bytes stored immediately next to it are much more likely to be accessed sooner than bytes that are not in the immediate vicinity of the recently accessed byte. For example, when a program is stored in RAM, the storage space in the RAM is filled up in the same way that bricks are laid down for a wall—one in front of the other until the row is completed, then another row on top. So, if each brick represents an instruction in a program and the first brick in the seventh row is “accessed,” then the most likely place for the next instruction in the program to be stored is in the second brick in the seventh row. This information is useful because when a processor stores a byte in its cache, it can also read the following bytes and store them in the cache. This will result in fewer accesses to the RAM and/or a hard drive. Since a cache is faster than other memory, the more frequently a processor can obtain the desired information from the cache, the faster the apparent speed of the processor.
Caching has been widely used in many applications, including, for example, in processor controlled graphics accelerators. Graphics accelerators cache texture images and generally achieve a very good performance due to a reduction in accesses to external memory. Texture images are inherently 2-dimensional data sets of size “width” by “height” measured in number of pixels. Each pixel in a texture image is addressed by coordinate data (u,v) where u represents the horizontal axis and v represents the vertical axis.
When caching a group of data, one of the key issues to resolve is where a group of data should be stored in the cache. In the simplest case, a cache with only one entry, there is no choice. For a cache with two entries, a decision has to be made about whether to save a group of data in entry 0 or entry 1. For a typical cache with 32, 64, 128 or more entries, the decision must follow a carefully designed cache addressing algorithm that yields desired results.
A cache address algorithm can be based on a variety of information. For example, for storing texture images, a cache address can be assigned to each texture image based on the texture image's address in main memory. Another approach uses the coordinates of the texture in the larger image to determine which cache address to use; this exploits the 2-dimensional nature of texture images.
A cache address algorithm can either be direct mapped or n-way associative. A direct mapping means that a group of bytes will be stored in the cache in 1 location only. This scheme is easy and cheap to implement, but it does not perform as well as n-way associative schemes. In a 2-way associative cache, a group of bytes will be stored in 1 of 2 possible locations. The choice of which location to use depends on the replacement algorithm which can be least recently used (the entry that has not been accessed for the longest period of time will be overwritten with the new entry), first in first out (the entry that has been written into the cache for the longest period of time will be overwritten), most recently used (the last entry to be accessed will be overwritten), etc. A 2-way scheme tends to perform better than a direct mapping algorithm, but it is also more complex because more information has to be considered before deciding on a cache address. More complex schemes use 4-way, 8-way, etc. all the way up to fully associative caches. The benefit of the more complex schemes is performance, but the cost, complexity, chip area, and design time detract from their desirability. Different cache addressing schemes may be better suited for different application programs.
One way that a direct mapping algorithm for caching 2-dimensional texture data can be improved significantly is by hashing the address. Hashing is a method of storing and retrieving data entries. Rather than storing an entry based on the data in the entry, a shorter data key is assigned based on the data. A shorter data key allows an entry to be found in less time than a longer string of data.
For storing texture images in a cache, the coordinate bits may be logically exclusive OR'd (XOR'd) together to form a cache address. There are many different ways to select which bits of the coordinate bits to XOR together, but once the choice is made, it is designed into the hardware and is unchangeable after a cache integrated circuit is fabricated. Many cache integrated circuits have several pre-determined cache addressing schemes to accommodate various caching modes and provide greater flexibility in performing caching function, but once the chip is fabricated, only the pre-determined modes can be used. If other cache addressing schemes are desired, they are not available.
Therefore, there exists a desire and a need for a method and apparatus for permitting the modification of cache address computation functions after a cache chip is fabricated.